home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-ietf-pip-processing-02.txt < prev    next >
Text File  |  1993-08-24  |  36KB  |  982 lines

  1.  
  2.  
  3. Network Working Group                                         P. Francis
  4. INTERNET-DRAFT                                       (formerly Tsuchiya)
  5.                                                                 Bellcore
  6.                                                              August 1993
  7.  
  8.  
  9.                          Pip Header Processing
  10.  
  11.  
  12. Changes Since Last Version
  13.  
  14.    This version has the following changes from the previous version,
  15.    dated November 1992.
  16.  
  17.    1.   The management of the HD and RC fields has changed (though the
  18.         semantics and evolvability of them has not).  The HD and RC
  19.         fields are still opaque (meaning that the semantics of the HD
  20.         and RC cannot be determined without additional information), but
  21.         Pip will operate globally under well-known sets of semantics,
  22.         and each packet indicates which set the packet falls under.  The
  23.         need to remap the HD and RC fields hop-by-hop has been elim-
  24.         inated (though tagging is still a feature of Pip).
  25.  
  26.    2.   This version has made options faster to process and more gen-
  27.         eral.  It has introduced fields in the fixed part of the Transit
  28.         Part to indicate which options are present, and the first option
  29.         now indicates where each individual option is in the list of
  30.         options.  In addition, the Transit Options part can now be in
  31.         the self-encapsulation header.
  32.  
  33.    3.   The router and host options have been combined into one options
  34.         part.
  35.  
  36.    4.   The entire Host Part has been moved into the Initial Part.
  37.  
  38.    5.   All checksums have been removed.
  39.  
  40.    6.   The FTIFs have been limited to a single length (16 bits).  No
  41.         that this does not limit a single "number" in the FTIF chain to
  42.         16 bits or less. A "number" can be encoded as mulitple FTIFs.
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52. Pip WG, Expires Feb. 23, 1994                                   [Page 1]
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59. INTERNET-DRAFT                 Pip Header                    August 1993
  60.  
  61.  
  62.    Status of this Memo
  63.  
  64.    This document is an Internet Draft.  Internet Drafts are working
  65.    documents of the Internet Engineering Task Force (IETF), its Areas,
  66.    and its Working Groups. Note that other groups may also distribute
  67.    working documents as Internet Drafts).
  68.  
  69.    Internet Drafts are draft documents valid for a maximum of six
  70.    months. Internet Drafts may be updated, replaced, or obsoleted by
  71.    other documents at any time.  It is not appropriate to use Internet
  72.    Drafts as reference material or to cite them other than as a "working
  73.    draft" or "work in progress."
  74.  
  75.    Please check the I-D abstract listing contained in each Internet
  76.    Draft directory to learn the current status of this or any other
  77.    Internet Draft.
  78.  
  79.  
  80. Abstract
  81.  
  82.    Pip is an internet protocol intended as the replacement for IP ver-
  83.    sion 4.  Pip is a general purpose internet protocol, designed to han-
  84.    dle all forseeable internet protocol requirements.  This specifica-
  85.    tion defines the Pip header processing for Routers and Hosts.
  86.  
  87.  
  88. Acknowledgements
  89.  
  90.    I want to individually acknowledge Rob Coltun, Steve Deering, Ramesh
  91.    Govindan, Joel Halpern, John Ioannidis, Chris Petrilli, Bob Smart,
  92.    and Zheng Wang.  I want also to acknowledge the many people from the
  93.    Pip working group who have participated in developing Pip.  Finally,
  94.    I want to acknowledge the SIP protocol (or, more accurately, the peo-
  95.    ple behind the SIP protocol) for providing certain good ideas.
  96.  
  97. Conventions
  98.  
  99.    All functions in this specification are mandatory.
  100.  
  101.  
  102.  
  103. 1.  Introduction
  104.  
  105.    Pip is an internet protocol intended as the replacement for IP ver-
  106.    sion 4.  Pip is a general purpose internet protocol, designed to
  107.  
  108.  
  109.  
  110. Pip WG, Expires Feb. 23, 1994                                   [Page 2]
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117. INTERNET-DRAFT                 Pip Header                    August 1993
  118.  
  119.  
  120.    handle all forseeable internet protocol requirements.  This specifi-
  121.    cation defines the Pip header processing for Routers and Hosts.
  122.  
  123.    The design of Pip is fundamentally different from that of previous
  124.    internetwork protocols.  Pip is designed to be as general as possi-
  125.    ble, but without significantly compromising performance.  Because of
  126.    Pip's generality, it can handle forseeable routing and addressing
  127.    requirements.  It is hoped that it will be able to handle most if not
  128.    all future routing and addressing requirements.
  129.  
  130.    There are many detailed aspects of Pip that provide this generality
  131.    that are not discussed here.  It is useful, however, to mention one
  132.    general aspect.  That is, Pip strives to remove as much "functional
  133.    semantics" from the base specification as possible.  Pip defines a
  134.    packet header and forwarding rules that can include many different
  135.    functional semantics (that is, routing, addressing, and flow para-
  136.    digms).  Therefore, the reader may often find him or herself asking
  137.    "But how do you do foo with Pip?" The answer to this sort of question
  138.    belongs in companion documents to the basic Pip spec.
  139.  
  140.    Pip can be thought of as a mechanism for triggering actions in hosts
  141.    and routers, just as a machine language can be thought of as a
  142.    mechanism for triggering actions in CPUs.  The machine language has
  143.    no functional semantics outside of the specific actions it triggers
  144.    (move this register, write that memory location, etc.).  But, the
  145.    machine language is a very powerful tool upon which functional seman-
  146.    tics are built.  Likewise, Pip is a powerful tool upon which routing,
  147.    addressing, and flow functions can be built.
  148.  
  149.  
  150.  
  151. 2.  Pip Specification
  152.  
  153.    The Pip header is partitioned into three parts, the Initial Part, the
  154.    Transit Part, and the Options Part.
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168. Pip WG, Expires Feb. 23, 1994                                   [Page 3]
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175. INTERNET-DRAFT                 Pip Header                    August 1993
  176.  
  177.  
  178.  
  179.            +===========================+
  180.            |       Initial Part        |
  181.            +===========================+
  182.            |       Transit Part        |
  183.            +===========================+
  184.            |       Options Part        |
  185.            +===========================+
  186.            |                           |
  187.            |         Payload           |
  188.            |                           |
  189.  
  190.  
  191.    Each part falls on a 32-bit boundary (as indicated by the double
  192.    lines shown), and the Transit Part falls on a 64 bit boundary.
  193.  
  194.    The concept of tunneling in an integral part of Pip.  Pip achieves
  195.    tunneling by encapsulating the Transit Part of the Pip header in
  196.    another Transit Part.  Therefore, when tunneling, there is one Tran-
  197.    sit Part for each (nested) tunnel:
  198.  
  199.            +===========================+
  200.            |       Initial Part        |
  201.            +===========================+
  202.            |       Transit Part        |
  203.            +===========================+
  204.            |       Transit Part        |
  205.            +===========================+
  206.                        .
  207.                        .
  208.                        .
  209.            +===========================+
  210.            |       Transit Part        |
  211.            +===========================+
  212.            |       Options Part        |
  213.            +===========================+
  214.  
  215.  
  216.    Because each Transit Part has only what is necessary for router for-
  217.    warding and handling, this method of tunneling is reasonably effi-
  218.    cient in terms of packet size.
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226. Pip WG, Expires Feb. 23, 1994                                   [Page 4]
  227.  
  228.  
  229.  
  230.  
  231.  
  232.  
  233. INTERNET-DRAFT                 Pip Header                    August 1993
  234.  
  235.  
  236. 2.1.  Initial Part
  237.  
  238.    The Initial Part is formatted as shown in Figure 1.
  239.  
  240.                                          length, in bits
  241.            +===========================+
  242.            |    Version Number = 8     |     4
  243.            +---------------------------+
  244.            |       Sub-Version         |     4
  245.            +---------------------------+
  246.            |      Options Offset       |     8
  247.            +---------------------------+
  248.            |     Options Contents      |     8
  249.            +---------------------------+
  250.            |     Options Present       |     8
  251.            +===========================+
  252.            |       Packet SubID        |     16
  253.            +---------------------------+
  254.            |         Protocol          |     16
  255.            +===========================+
  256.            |         Dest ID           |     64
  257.            +===========================+
  258.            |        Source ID          |     64
  259.            +===========================+
  260.            |      Payload Length       |     32
  261.            +===========================+
  262.            |       Host Version        |     8
  263.            +---------------------------+
  264.            |      Payload Offset       |     8
  265.            +---------------------------+
  266.            |        Hop Count          |     16
  267.            +===========================+
  268.  
  269.                           Figure 1:  Initial Part
  270.  
  271.    An explanation of each field follows.
  272.  
  273.  
  274.    2.1.1.  Version Numbers
  275.  
  276.    The first octet is divided into two 4-bit fields, the Version and the
  277.    Sub-Version.  The Version field is set to be 8, and is meant to be
  278.    version 8 of IP.  (As of this writing, this is an experimental number
  279.    assigned for development of Pip.) Thus, all encapsulation schemes
  280.    defined for IP can work for Pip as well.
  281.  
  282.  
  283.  
  284. Pip WG, Expires Feb. 23, 1994                                   [Page 5]
  285.  
  286.  
  287.  
  288.  
  289.  
  290.  
  291. INTERNET-DRAFT                 Pip Header                    August 1993
  292.  
  293.  
  294.    As long as the Version field is 8, the Initial Part and Options Part
  295.    of the Pip Header is as specified in this standard.  (In other words,
  296.    the Sub-Version field refers only to the Transit Part.)
  297.  
  298.    By doing this, we allow the Transit Part of the Pip Header to change
  299.    completely without necessarily requiring a host to understand the new
  300.    Transit Part.  If a host receives a Pip header with a Version number
  301.    of 8 and an unknown Sub-version number, the host does not try to
  302.    parse the Transit Part at all, rather it processes only the Initial
  303.    Part and the Options Part.  (By using the Pip Header Protocol to for-
  304.    mat Pip Headers, a host can be made to formulate the right Transit
  305.    Part, even though the host doesn't understand the semantics of the
  306.    Transit Part.  This allows radical migration of the Transit Part
  307.    while potentially not requiring changes to hosts.)
  308.  
  309.    If a host or a router receives a packet with an unknown Version
  310.    number, the packet is silently discarded.
  311.  
  312.    The Sub-Version field is set to the value 0 for the version of Pip
  313.    defined in this specification.  As long as the Sub-Version number is
  314.    0, the Transit Part is as specified in this standard.  Any packet
  315.    received by a router with a Version number of 8 and an unknown Sub-
  316.    Version number is silently discarded.
  317.  
  318.  
  319.    2.1.2.  Options Offset
  320.  
  321.    The Options Offset indicates the position of the Options Part.  The
  322.    unit of measure of the Options Offset is 32-bit words, counting the
  323.    first word of the Pip Header as word 0.
  324.  
  325.  
  326.    2.1.3.  Options Contents
  327.  
  328.    This field indicates how the Options Present field should be inter-
  329.    preted.  Each bit of the Options field indicates if each of up to
  330.    eight options is present in the Options Part.  The Options Contents
  331.    field indirectly indicates which option each bit of the Options
  332.    Present field refers to.  We say indirectly because the mapping
  333.    referred to by the Options Contents field is stored locally. In other
  334.    words, without additional information (the mapping), it is not possi-
  335.    ble to examine the Options Contents field and know what option each
  336.    bit of the Options Present field refers to.
  337.  
  338.    Any of 256 possible Options Contents values can be active at a given
  339.  
  340.  
  341.  
  342. Pip WG, Expires Feb. 23, 1994                                   [Page 6]
  343.  
  344.  
  345.  
  346.  
  347.  
  348.  
  349. INTERNET-DRAFT                 Pip Header                    August 1993
  350.  
  351.  
  352.    time.  (Note that the means by which the meaning of the Options Con-
  353.    tents values are assigned and conveyed to routers and hosts is out-
  354.    side the scope of this specification.)
  355.  
  356.  
  357.    2.1.4.  Options Present
  358.  
  359.    This field indicates which of the Options indicated by the Options
  360.    Contents field are actually present in the Options Part.  Each bit of
  361.    this field refers to a single option type.  The mapping of each bit
  362.    to its' option type is determined by the Options Contents field.
  363.  
  364.    For instance, assume that the Options Contents field indicates that
  365.    bit 0 of the Options Present field refers to the PDN Address option,
  366.    that bit 1 of the Options Present field refers to the foo option, and
  367.    that bit 2 of the Options Present field refers to the Fragmentation
  368.    option.  (As of this writing, there is only one option.  Until there
  369.    are more than eight options, there is no need to define more than one
  370.    Options Contents values.)
  371.  
  372.    In this case, a value of 101 in the Options Present field indicates
  373.    that the PDN Address and Fragmentation options are present in the
  374.    Options Part, and that the foo option is not present.
  375.  
  376.    Note that an Options Present value of 0 indicates that there are no
  377.    options present, regardless of the value of the Options Contents
  378.    field.  Note also that no more than 8 options, not including the
  379.    default first option (the Options Descriptor), can be present in any
  380.    Options Part.
  381.  
  382.    The Options Contents/Options Present method of processing options
  383.    allows for efficient processing of options.  First, a router can
  384.    ignore any options that may be present but that do not impact it (for
  385.    instance, a router not attached to a PDN need not consider the PDN
  386.    Address option).  Second, the desired option can be very quickly
  387.    retrieved, because the first option, the Options Descriptor option,
  388.    contains the offset of each of the up to eight options indicated by
  389.    the Options Present field.
  390.  
  391.  
  392.    2.1.5.  Packet SubID
  393.  
  394.    This field is used by Pip hosts to correctly associate received PCMP
  395.    messages with local control blocks.  This is necessary because the
  396.    semantics of the Transit Part can change while a packet is in
  397.  
  398.  
  399.  
  400. Pip WG, Expires Feb. 23, 1994                                   [Page 7]
  401.  
  402.  
  403.  
  404.  
  405.  
  406.  
  407. INTERNET-DRAFT                 Pip Header                    August 1993
  408.  
  409.  
  410.    transit.  Therefore, a router sending a PCMP message cannot neces-
  411.    sarily provide all of the information needed by the Pip host to
  412.    correctly identify the context of the received message (that is,
  413.    which "packet flow" it is identified with).
  414.  
  415.    A PCMP message uses the Protocol, Source ID, Dest ID, and Packet
  416.    SubID to define the PCMP messages context.  It is not sufficient to
  417.    use just Protocol, Source ID, and Dest ID, because two hosts running
  418.    the same protocol between them may have multiple "flows", for
  419.    instance, a data flow, a video flow, and an audio flow in the case of
  420.    multi-media.  Each flow may have a different Transit Part, and take
  421.    different paths.  Therefore, the Packet SubID field is needed to
  422.    further differentiate.
  423.  
  424.  
  425.    2.1.6.  Protocol
  426.  
  427.    Indicates the protocol header found in the payload.  The values for
  428.    this field are the same as those used for IPv4.
  429.  
  430.  
  431.    2.1.7.  Dest ID
  432.  
  433.    The Dest ID field indicates the Pip ID of the final recipient of the
  434.    Pip packet.  This field is examined by both hosts and routers.
  435.  
  436.    When a Pip System processes the Routing Directive (RD), it may deter-
  437.    mine that it needs to examine the Dest ID for further processing.
  438.    This may happen both when a host or router receives a Pip packet des-
  439.    tined for itself, or when a router receives a packet that should be
  440.    forwarded based on Dest ID (as indicated by the RD).
  441.  
  442.    When a Pip system determines at forwarding time that a packet is des-
  443.    tined for itself, it checks the Dest ID to verify if that packet is
  444.    destined for it.  If the complete Dest ID matches one of its own Pip
  445.    IDs, then the packet is for it, and is passed to the layer indicated
  446.    by the Protocol field (in the Host Part).  (The Pip system may of
  447.    course wish to check a security option before passing a packet to an
  448.    upper layer.)
  449.  
  450.    If the complete Dest ID field does not match one of its own IDs, then
  451.    an ID/RD Mismatch PCMP message is sent to the source of the packet,
  452.    as indicated by the Source ID and potentially source information in
  453.    the RD.  The purpose of this message is to flush the ID to RD binding
  454.    in the source Pip host.
  455.  
  456.  
  457.  
  458. Pip WG, Expires Feb. 23, 1994                                   [Page 8]
  459.  
  460.  
  461.  
  462.  
  463.  
  464.  
  465. INTERNET-DRAFT                 Pip Header                    August 1993
  466.  
  467.  
  468.    2.1.8.  Source ID
  469.  
  470.    This is the Pip ID of the source of the packet.  It is passed to
  471.    upper layers for the purposes of identifying the context for the
  472.    packet.
  473.  
  474.  
  475.    2.1.9.  Payload Length
  476.  
  477.    The Payload Length gives the length of the Pip packet payload in
  478.    units of 8 bits.  The Payload Length does not include the length of
  479.    the Pip header.
  480.  
  481.  
  482.    2.1.10.  Host Version
  483.  
  484.    The Host Version field indicates what "version" of Pip software the
  485.    sending host has implemented.  This is to allow a host to inform a
  486.    router which ancillary protocols/messages the host is able to accept.
  487.    It is envisioned that over time, new host functions will be
  488.    developed.  Different hosts will install these new functions at dif-
  489.    ferent times.  This field allows routers to know what functions the
  490.    host can and cannot handle.
  491.  
  492.  
  493.    2.1.11.  Payload Offset
  494.  
  495.    The Payload Offset indicates the position of the Payload Part.  The
  496.    unit of measure of the Payload Offset is 32-bit words, counting the
  497.    first word of the Pip Header as word 0.
  498.  
  499.    If a Pip system encapsulates a Transit Part in another Transit Part,
  500.    then the Payload Offset is increased by the length of the new Transit
  501.    Part.
  502.  
  503.  
  504.    2.1.12.  Hop Count
  505.  
  506.    The Hop Count is decremented by every router that forwards the Pip
  507.    packet.  If a system receives a Pip header with a Hop Count equal to
  508.    0, and is not the recipient of the packet, then the packet is dis-
  509.    carded and a PCMP Destination Unreachable is routed to the system
  510.    indicated by the Routing Directive.  (In other words, a host can
  511.    legally receive a Transit Part with a Hop Count of 0, and indeed a
  512.    host doesn't look at the Hop Count field upon reception.)
  513.  
  514.  
  515.  
  516. Pip WG, Expires Feb. 23, 1994                                   [Page 9]
  517.  
  518.  
  519.  
  520.  
  521.  
  522.  
  523. INTERNET-DRAFT                 Pip Header                    August 1993
  524.  
  525.  
  526. 2.2.  Transit Part
  527.  
  528.    The Transit Part is formatted as shown in Figure 2.
  529.  
  530.  
  531.                                          length, in bits
  532.                    +===========================+
  533.                    |         Reserved          |     16
  534.                    +---------------------------+
  535.                    |    Transit Part Offset    |     8
  536.                    +---------------------------+
  537.                    |        HD Contents        |     8
  538.                    +===========================+
  539.                    |  Handling Directive (HD)  |     32
  540.     ---------------+===========================+
  541.         ^          |        FTIF Offset        |     8
  542.         |          +---------------------------+
  543.         |          |        RC Contents        |     8
  544.         |          +---------------------------+
  545.         |          |   Routing Context (RC)    |     16
  546.      Routing       +===========================+
  547.                    |         FTIF 1            |     16
  548.      Directive     +---------------------------+
  549.         |          |         FTIF 2            |     16
  550.         |          +---------------------------+
  551.         |                       .
  552.         |                       .
  553.         |                       .
  554.         |          +---------------------------+
  555.         |          |         FTIF N            |     16
  556.         |          +---------------------------+
  557.         v          |         Padding           |     Variable
  558.     ---------------+===========================+
  559.  
  560.                           Figure 2: Transit Part
  561.  
  562.  
  563.  
  564.    An explanation of each field follows.
  565.  
  566.  
  567.    2.2.1.  Transit Part Offset
  568.  
  569.    This field gives the position of the first word of the next Transit
  570.    Part.  The unit of measure of the Transit Part Offset is 32-bit
  571.  
  572.  
  573.  
  574. Pip WG, Expires Feb. 23, 1994                                  [Page 10]
  575.  
  576.  
  577.  
  578.  
  579.  
  580.  
  581. INTERNET-DRAFT                 Pip Header                    August 1993
  582.  
  583.  
  584.    words, counting the first word of the current Transit Part as word 0.
  585.    If there is no next Transit Part, then this field is written as all
  586.    0's.
  587.  
  588.  
  589.    2.2.2.  HD Contents
  590.  
  591.    He HD Contents field indicates how the Handling Directive (HD) field
  592.    should be interpreted.  The HD field is divided into multiple fields,
  593.    each representing a different handling function.  Each individual
  594.    field in the HD is called an HD Unit (HDU).  The Options Contents
  595.    field indirectly indicates which HDUs are in the HD field, and where
  596.    they are.  We say indirectly because the mapping referred to by the
  597.    HD Contents field is stored locally. In other words, without addi-
  598.    tional information (the mapping), it is not possible to examine the
  599.    HD Contents field and know what the HDU locations are.
  600.  
  601.    Any of 256 possible HD Contents values can be active at a given time.
  602.    (Note that the means by which the meaning of the HD Contents values
  603.    are assigned and conveyed to routers and hosts is outside the scope
  604.    of this specification.)
  605.  
  606.  
  607.    2.2.3.  Handling Directive (HD)
  608.  
  609.    The HD is a general purpose field used for the purpose of triggering
  610.    special packet handling by a Pip system.  The HD field does not
  611.    influence a Pip router's next hop choice for a Pip packet, nor does
  612.    it influence a Pip host's determination as to whether the Pip packet
  613.    is destined for it.  Examples of special packet handling would be
  614.    "low priority queueing", or "high priority discard", etc.  (Note that
  615.    the Transit Options also influence "handling", in the sense that han-
  616.    dling is essentially defined here to mean "anything that is not rout-
  617.    ing.  The HD field, though, is intended for the most common types of
  618.    handling--handling that is expected to be in a significant percentage
  619.    of packets.)
  620.  
  621.    Both hosts and routers use the HD field.  (Hosts may make use of the
  622.    HD field for packet handling for both incoming and outgoing packets.)
  623.  
  624.    There is a complete distinction between the syntax and the semantics
  625.    of the HD field.  (This can be contrasted with, for instance, IP,
  626.    which couples the semantics and syntax of the TOS bits.  That is, the
  627.    IP specification itself determines, to a first degree, how the TOS
  628.    bits are interpreted.) Each Pip system can modify the semantic
  629.  
  630.  
  631.  
  632. Pip WG, Expires Feb. 23, 1994                                  [Page 11]
  633.  
  634.  
  635.  
  636.  
  637.  
  638.  
  639. INTERNET-DRAFT                 Pip Header                    August 1993
  640.  
  641.  
  642.    meaning of the HD, for instance, by increasing or decreasing the
  643.    queueing priority of a packet.  This is called packet tagging.
  644.  
  645.    From an abstract modeling perspective, the HD is handled as follows:
  646.  
  647.    1.   Extract the semantic meaning(s) (the handling instructions asso-
  648.         ciated with the HDUs) from the HD field.  Transmitting Pip hosts
  649.         determine the semantic meaning by some other means, such as the
  650.         upper layer protocol.  If the receiving system decapsulates mul-
  651.         tiple Pip headers, then the HD semantics are extracted from the
  652.         lowest Pip header for which it is not the target (see example on
  653.         tunneling below).
  654.  
  655.    2.   Handle the Pip packet according to those instructions.  In some
  656.         cases, it is possible that the Pip system does not understand
  657.         the semantics of one or more HDUs of the HD field.  For each HDU
  658.         whose semantics are not understood, however, the pip system at
  659.         least knows whether to 1) pass the HDU on untouched, 2) set it
  660.         to all 0s, 3) set it to all 1s, 4) discard the packet silently,
  661.         or 5) discard the packet with a PCMP HDU Not Understood packet.
  662.  
  663.    3.   Modify the semantic meaning if necessary.  Note also that if the
  664.         Pip packet is replicated for multicast, each packet has its HD
  665.         semantics modified individually.
  666.  
  667.  
  668.  
  669.    2.2.4.  Tunneling
  670.  
  671.    Consider two Pip systems, X and Y, separated by one or more inter-
  672.    mediate Pip systems.  X wishes to tunnel a Transit Part to Y.  Y is
  673.    therefore the target system of the tunnel.  A Transit Part He arrives
  674.    at X.  In order to forward the Transit Part to Y, X encapsulates He
  675.    in another Transit Part, Hy.  Y is the target system for Transit Part
  676.    Hy.  X sets the HD of He to what it would have been if Y was directly
  677.    connected to X (that is, there were no intermediate Pip systems
  678.    between X and Y).  Further, it is intended that Y will derive its HD
  679.    semantics from the HD of Transit Part He, not Transit Part Hy.
  680.  
  681.  
  682.  
  683.         ----0-----o-----o-----o-----o-----0----
  684.             X     I     J     K     L     Y
  685.  
  686.  
  687.  
  688.  
  689.  
  690. Pip WG, Expires Feb. 23, 1994                                  [Page 12]
  691.  
  692.  
  693.  
  694.  
  695.  
  696.  
  697. INTERNET-DRAFT                 Pip Header                    August 1993
  698.  
  699.  
  700.    Now consider the operation of Pip system L (the previous hop system
  701.    to Y).  When L forwards the packet to Y, it may either decapsulate
  702.    the packet (in the knowledge that Y is the target for Hy), or not
  703.    decapsulate the packet.  Either way, L derives its HD semantics from
  704.    the HD of Transit Part He.
  705.  
  706.    If L does not decapsulate the Transit Part, then it is as though I,
  707.    J, K, and L are a "subnetwork" (albeit a Pip subnetwork), and Y is
  708.    stripping the "subnetwork" header (Hy) off before processing the true
  709.    Transit Part (He).  If L does decapsulate the Transit Part, then,
  710.    from Y's perspective, it is essentially as though Y were directly
  711.    connected to X.
  712.  
  713.  
  714.    2.2.5.  Routing Directive (RD)
  715.  
  716.    The RD consists of the Routing Context (RC), the RC Contents, the
  717.    FTIF Offset, and a series of zero or more FTIFs (Forwarding Table
  718.    Index Fields).  This series of FTIFs is called the FTIF Chain.  The
  719.    sole purpose of the RD is to determine how to forward the Pip
  720.    packet--the RD does not influence handling in any way.
  721.  
  722.    Figure 3 illustrates the decision process for forwarding the Pip
  723.    packet.
  724.  
  725.  
  726.  
  727.    Figure 3 is interpreted as follows.  The FIB is the Forwarding Infor-
  728.    mation Block.  The FIB contains all the information needed to forward
  729.    a packet, and may contain multiple next hop (for multicast).  This
  730.    information includes 1) the outgoing interface, 2) how to encapsulate
  731.    the packet, including lower-layer address(es) (the lower-layer
  732.    address(es) along with the outgoing interface determine the next hop
  733.    Pip system), 3) whether and how to tunnel, 4) how to modify the
  734.    semantics of the HD and RC, and how to modify the FTIF Offset.  The
  735.    goal of the forwarding algorithm is to reach the appropriate FIB.
  736.  
  737.    The directed lines in Figure 3 start at the RC and, through various
  738.    possible paths, reach a FIB.  These lines represent the various
  739.    information that can influence the forwarding decision (that is, the
  740.    FIB chosen).  For instance, there is no way to reach a FIB without
  741.    first examining the information in the RC.  However, it is possible
  742.    to identify a FIB by considering only the information in the RC (as
  743.    indicated by the directed line leading directly right from the RC).
  744.    Based on the information in the RC, it is also possible to determine
  745.  
  746.  
  747.  
  748. Pip WG, Expires Feb. 23, 1994                                  [Page 13]
  749.  
  750.  
  751.  
  752.  
  753.  
  754.  
  755. INTERNET-DRAFT                 Pip Header                    August 1993
  756.  
  757.  
  758.  
  759.                  +---------+(next level RC)
  760.     (decapsulate)|         |
  761.                  |         v
  762.                  |<--------RC----------------->FIB
  763.                  |        /              |       |    IF Offset)
  764.                  |       |     |
  765.                  |       |     v
  766.                  |<------|---FTIF------------->FIB
  767.                  |       |  /  :
  768.                  |       |<-   :(repeatedly...)
  769.                  |       |     :
  770.                  |       |     v
  771.                  |<------|---FTIF------------->FIB
  772.                          |  /  |
  773.                          |<-   |
  774.                          v     v
  775.                           DestID-------------->FIB
  776.  
  777.                        Figure 3:  Forwarding Process
  778.  
  779.  
  780.    that the Transit Part must be decapsulated, and 1) the RC of the next
  781.    Transit Part be processed (the line leading directly left), 2) the
  782.    FTIF indicated by the FTIF Offset is processed (the line leading down
  783.    and right), or 3) the Dest ID is processed (the line leading down and
  784.    lest).
  785.  
  786.    Likewise, when considering the value of an FTIF (in addition to all
  787.    information already considered), the resulting action may be that 1)
  788.    a FIB is identified, 2) the Transit Part is decapsulated, 3) the sub-
  789.    sequent FTIF is processed, or 4) the Dest ID is processed.
  790.  
  791.    The RC is handled similarly to the HD.  The RC Contents field indi-
  792.    cates how the RC should be interpreted.  While the RC is constructed
  793.    similarly to the HD in the sense that it consists of multiple fields,
  794.    the RC can be interpreted as a flat field in-so-far as forwarding a
  795.    Pip packet is concerned, whereas the HD cannot.
  796.  
  797.    Thus, in a mechanical sense, the RC Contents can be viewed as an
  798.    index into a table that returns a pointer to another table (an
  799.    rcTable), which is indexed by the RC itself.  (Or, the combined RC
  800.    Contents/RC can be viewed as a single large index into a single
  801.    table, etc.)
  802.  
  803.  
  804.  
  805.  
  806. Pip WG, Expires Feb. 23, 1994                                  [Page 14]
  807.  
  808.  
  809.  
  810.  
  811.  
  812.  
  813. INTERNET-DRAFT                 Pip Header                    August 1993
  814.  
  815.  
  816.    The FTIF Offset field indicates which FTIF is active.  The active
  817.    FTIF is the one that is used to index the forwarding table indicated
  818.    by the RC Contents/RC.  An FTIF Offset value of 0 means that the
  819.    first FTIF is active, an FTIF Offset value of 1 means that the second
  820.    FTIF is active, and so on.  If there are no FTIFs, then the FTIF
  821.    Offset has no meaning, and can be any value.  In this case, the RC
  822.    field itself will indicate how to forward the packet.
  823.  
  824.    The FTIF Chain is padded out to a 32-bit boundary.  Note that there
  825.    can be more than 16 bits of padding (for instance, if it is desirable
  826.    to pad out to a 64-bit boundary).  The padding is ignored upon
  827.    receipt, and can be transmitted as any value (that is, it does not
  828.    have to be any specific pattern of 0's or 1's).
  829.  
  830.    Note that a single "number" in the FTIF chain may in fact be more
  831.    than 16 bits in length.  In this case, the number can be encoded as
  832.    multiple FTIFs with no loss of generality.  It is only required that
  833.    in all cases a multiple FTIF number be distinguishable from a single
  834.    FTIF number.
  835.  
  836.  
  837.    2.2.6.  Router RD Forwarding Algorithm
  838.  
  839.    This section describes the forwarding algorithm for a Pip router.
  840.  
  841.    1.   Using the value of the RC field as an index, retrieve one of the
  842.         following instructions (steps 2 - 5) from the rcTable determined
  843.         by the RC Contents.
  844.  
  845.    2.   If the instruction is decapsulate, then decapsulate the Transit
  846.         Part and re-execute step 1 using the next Transit Part.
  847.  
  848.    3.   If the instruction is forward, then retrieve the associated For-
  849.         warding Information Block (FIB), and go to step 12.
  850.  
  851.    4.   If the instruction is to examine the Dest ID, then retrieve the
  852.         FIB associated with the Dest ID, and go to step 12.
  853.  
  854.    5.   If the instruction is to examine the FTIF Chain, then retrieve
  855.         the forwardingTable indicated by the rcTable entry, and continue
  856.         on to step 6.
  857.  
  858.    6.   Using the value of the currently active FTIF (this is the FTIF
  859.         indicated by the FTIF Offset if this is the first FTIF examined)
  860.         as an index, retrieve one or more of the following instructions
  861.  
  862.  
  863.  
  864. Pip WG, Expires Feb. 23, 1994                                  [Page 15]
  865.  
  866.  
  867.  
  868.  
  869.  
  870.  
  871. INTERNET-DRAFT                 Pip Header                    August 1993
  872.  
  873.  
  874.         (steps 7 - 10) from the forwardingTable identified in step 5 or
  875.         step 10.
  876.  
  877.    7.   If the instruction is decapsulate, then decapsulate the Pip
  878.         header and re-execute step 1 using the new header (this is the
  879.         same as step 2).
  880.  
  881.    8.   If the instruction is forward, then (possibly additionally)
  882.         retrieve the associated FIB, and go to step 12 (this is the same
  883.         as step 3).
  884.  
  885.    9.   If the instruction is to examine the Dest ID, then retrieve the
  886.         FIB associated with the Dest ID and go to step 12 (this is the
  887.         same as step 4).
  888.  
  889.    10.  If the instruction is to examine the next FTIF, then, according
  890.         to the information in the current forwardingTable entry, modify
  891.         the current FTIF and choose a new forwardingTable.
  892.  
  893.    11.  Make the next FTIF the current FTIF and go to step 6.
  894.  
  895.    12.  The FIB contains a set of potential recipients for the Pip
  896.         packet, including next hop Pip systems (both directly connected
  897.         and at the end of Pip tunnels) and the upper layer of the local
  898.         system.  Taking into consideration 1) the incoming interface, 2)
  899.         the previous hop Pip system if known (as determined by the
  900.         lower-layer source address and incoming interface), and 3)
  901.         potentially other local information (such as congestion on out-
  902.         going queues), prune the set of potential recipients.  (This may
  903.         result in no pruning having taken place or in every potential
  904.         next hop having been pruned.)
  905.  
  906.    13.  For each remaining next hop, format a Pip header by modifying a)
  907.         the RC, b) the current FTIF, c) the FTIF Offset (to point to 1)
  908.         the FTIF pointed to in the received RD, 2) the current FTIF, 3)
  909.         the Nth FTIF counting from the 0th FTIF, or 4) the Nth FTIF
  910.         counting forwards or backwards from the current FTIF) and d) any
  911.         Pip header encapsulations, according to the information in the
  912.         FIB, and transmit the packet to the recipient (either a next hop
  913.         or upper layer).
  914.  
  915.  
  916.  
  917.  
  918.  
  919.  
  920.  
  921.  
  922. Pip WG, Expires Feb. 23, 1994                                  [Page 16]
  923.  
  924.  
  925.  
  926.  
  927.  
  928.  
  929. INTERNET-DRAFT                 Pip Header                    August 1993
  930.  
  931.  
  932. 2.3.  Options Part
  933.  
  934.    The Option Part is formatted as shown in Figure 4.
  935.  
  936.            +===========================+
  937.            |    Options Descriptor     |     64
  938.            +===========================+
  939.            |        Option 2           |     Variable
  940.            +===========================+
  941.            |        Option 3           |     Variable
  942.            +===========================+
  943.                        .
  944.                        .
  945.                        .
  946.            +===========================+
  947.            |        Option N           |     Variable
  948.            +===========================+
  949.  
  950.                           Figure 4: Options Part
  951.  
  952.  
  953.    Every Option is at least one 32-bit word in length, and ends on a
  954.    32-bit word boundary.  Because the type of each option is known from
  955.    the Options Contents field, there is no need to indicate the option
  956.    type in the options field themselves.  Thus, there is no common for-
  957.    mat among the options--each option has its own format.  The indivi-
  958.    dual options are defined in another specification.
  959.  
  960.  
  961.  
  962.    2.3.1.  Options Descriptor
  963.  
  964.    The Options Descriptor option gives the offset of each option in the
  965.    Options Part.  The Options Descriptor consists of eight eight-bit
  966.    Option Position fields, each of which gives the position of up to
  967.    eight options (there can be no more than 8 Options Part).  Each of
  968.    the Option Position fields correspond to one of the bits in the
  969.    Options Present field.  The unit of measure of each Option Position
  970.    is 32-bit words, counting the first word of the Options Part as word
  971.    0.  The high order Option Position field corresponds to the high
  972.    order bit in the Options Present field.
  973.  
  974.  
  975.  
  976.  
  977.  
  978.  
  979.  
  980. Pip WG, Expires Feb. 23, 1994                                  [Page 17]
  981.  
  982.